package com.TheEndWork;

import java.util.List;
import java.util.Scanner;

/**
 * @authoer zsj
 * @date 2022/5/27 17:13
 * <p>
 * 因为十分重要
 * 用中文命名来标志
 * <p>
 * 1思考出状态转移公式
 * 2初始化dp数组
 * 3实现动态转移公式
 */
public class 经典算法之动态规划 {

    /**
     * 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。
     * 该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
     */
    //动态规划解决
    public int fib(int n) {
        if (n <= 1) return 0;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i < n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }


    /**
     * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     * 子数组 是数组中的一个连续部分。
     */
    public static int maxSubArray(int[] nums) {
        int res = nums[0];
        int sum = 0;
        for (int num : nums) {
            if (sum > 0)
                sum += num;
            else
                sum = num;
            res = Math.max(res, sum);
        }
        return res;
    }


    /**
     * 给定一个数组 prices ，它的第i 个元素prices[i] 表示一支给定股票第 i 天的价格。
     * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。
     * 设计一个算法来计算你所能获取的最大利润。
     * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
     * <p>
     * 715364
     * 动态规划 前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}
     * ====================================================================
     * 记录【今天之前买入的最小值】
     * 计算【今天之前最小值买入，今天卖出的获利】，也即【今天卖出的最大获利】
     * 比较【每天的最大获利】，取最大值即可
     */
    public static int maxProfit(int[] prices) {
        if (prices.length <= 1) return 0;
        int min = prices[0];
        int max = 0;
        //状态转移方程
        //最大利润 = max(今天的股价 -  过去最低的股价,最大利润)
        //最低股价 = min(今天的股价,最低股价)
        for (int i = 1; i < prices.length; i++) {
            max = Math.max(max, prices[i] - min);
            min = Math.min(min, prices[i]);
        }
        return max;
    }

    /**
     * 给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。
     * 玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。
     * 每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），
     * 取到的数字将会从数组中移除（数组长度减 1 ）。
     * 玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。
     * 如果玩家 1 能成为赢家，返回 true 。
     * 如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。
     * <p>
     * 思路：
     * 为了判断哪个玩家可以获胜，需要计算一个总分，即先手得分与后手得分之差。
     * 当数组中的所有数字都被拿取时，如果总分大于或等于 0，则先手获胜，反之则后手获胜。
     */
    public boolean PredictTheWinner(int[] nums) {
        if (nums.length % 2 == 0 || nums.length == 1) return true;
        //到这里就说明数组为奇数

        return false;
    }

    /**
     * Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有 正 整数颗石子，数目为 piles[i]。
     * 游戏以谁手中的石子最多来决出胜负。石子的 总数 是 奇数 ，所以没有平局。
     * Alice 和 Bob 轮流进行，Alice 先开始 。
     * 每回合，玩家从行的 开始 或 结束 处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中 石子最多 的玩家 获胜 。
     * 假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回true，当 Bob 赢得比赛时返回false。
     * <p>
     * 他妈的   如果数组是偶数的话，而且每次都能选择最优选，那先手是必赢的，题目又说没有平局，玩毛
     */
    public boolean stoneGame(int[] piles) {
        int head = 0;
        int end = piles.length - 1;
        int a = 0, b = 0;
        while (head < end) {
            if (piles[head] > piles[end]) {
                //如果头部的石子数大于
                a += piles[head];
                b += piles[end];
                end--;
                head++;
            } else if (piles[head] < piles[end]) {
                //如果头部的石子数少
                a += piles[end];
                b += piles[head];
                end--;
                head++;
            }
        }
        return a > b;
    }

    /**
     * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
     * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额
     * <p>
     * 思路:
     * 假设一共有i间房子，那么能偷到的最大金额为dp[i]
     * 因为不能偷相邻的房子,所以我们有两种情况
     * 1  偷最后一家房子的话，最大金额 = 倒数第三家的金额 + 最后一家人的金额  dp[i] = dp[i-2]+nums[i]
     * 2  不偷最后一家的房子的话，最大金额 = 倒数第二个所偷的金额总量  dp[i] = dp[i-1]
     * 得出状态转移公式     dp[i] = max(dp[i-2]+nums[i],dp[i-1])
     */
    public static int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        int[] dp = new int[nums.length];
        //初始化dp数组
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        //dp[i] = max(dp[i-2]+nums[i],dp[i-1])
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[nums.length - 1];
    }

    /**
     * 给定一个三角形 triangle ，找出自顶向下的最小路径和。
     * 每一步只能移动到下一行中相邻的结点上。
     * 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，
     * 如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
     * <p>
     * 思路:
     * dp[i][j]就是结果,是最后结尾的值
     * 模拟
     * 1 [0][0]
     * 23   min([0+1][0+1],[0+1][0])
     * 456
     * 7891
     * 12345
     * <p>
     * <p>
     * 1
     * 34
     * 789
     * 14 15 17 9
     * <p>
     * <p>
     * 最终的最小的结果是由前一个最小的结果决定的
     * 而前一个最小的结果有两种
     * 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
     * 1、dp[i][j] = dp[i-1][j] + triangle.get(i).get(j)
     * 2、dp[i][j] = dp[i-1][j-1] + triangle.get(i).get(j)
     * dp[i][j] = min(dp[i-1][j] + triangle.get(i).get(j),dp[i-1][j-1] + triangle.get(i).get(j))
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();//得到有多少行
        int[][] dp = new int[n][n];
        dp[0][0] = triangle.get(0).get(0);
        //遍历顺序，正序遍历，因为题目要求从顶部开始到底部，而三角形的顶部是一定只有一个元素的
        for (int i = 1; i < n; i++) {
            //三角形是第n行就有n个数字
            //需要提前赋值
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
            for (int j = 0; j < i; j++) {
                //计算当前第i行第j个元素的最小路径值
                dp[i][j] = Math.min(dp[i - 1][j] + triangle.get(i).get(j), dp[i - 1][j + 1] + triangle.get(i).get(j));
            }
            dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
        }

        int min = dp[n - 1][0];
        //遍历最后一行的值得到最小值
        for (int i = 1; i < triangle.get(n - 1).size(); i++) {
            min = Math.min(min, dp[n - 1][i]);
        }
        return min;
    }

//
//    public static void main(String[] args) {
//        int[] arr = {1, 3, 1};
//        System.out.println(rob(arr));
//    }


    /**
     * 给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。
     * 整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x
     * <p>
     * 思路就是：
     * 这个数字首先必须是4的倍数,也就是 n%4 ==0
     * 这个数字如果是1的话直接返回true,因为任何数的0次幂都是1
     * 这个数字不能小于或者等于0,因为4的次幂中不可能有负数和0
     * <p>
     * 我们将这个数字一直/4 然后无限循环上面的条件就可以得到结果
     */
    public boolean isPowerOfFour(int n) {
        if (n == 1) return true;
        if (n <= 0) return false;
        if (n % 4 != 0) return false;
        //n==4的x次方
        return isPowerOfFour(n / 4);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] coins = new int[n][n];
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                coins[i][j] = scanner.nextInt();
            }
        }
        dp[0][0] = coins[0][0];
        for (int i = 1; i < n; i++) {
            dp[0][i] = coins[0][i] + dp[0][i - 1];
            dp[i][0] = coins[i][0] + dp[i - 1][0];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + coins[i][j];
            }
        }
        int max = 0;
        for (int[] ints : dp) {
            for (int anInt : ints) {
                max = Math.max(anInt, max);
                System.out.println(anInt);
            }
        }
        System.out.println(max);
    }

    /**
     * 　有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。
     * 你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。
     */
    public static void jinBi() {

    }
}
